# Классы типов

[Статья вышла на хабре](https://habr.com/ru/articles/771896).

## Что такое класс типов?

Давайте разберем, что такое класс типов. Обратимся к формальному определению:

> Класс типов (type class) — это абстрактный параметризованный тип,
> который позволяет добавлять новое поведение к любому закрытому типу данных без использования подтипов.

Класс типов - это в первую очередь про _"поведение"_.
Когда мы определяем класс типов, то неявно заключаем "контракт",
в котором описываем желаемое для определяемого класса типов поведение.

Является ли классом типов следующее определение?

```dotty
trait Something[A, B]:
  def doSomething(x: A): B
```

Формально - да. Здесь есть какое-то определение какого-то поведения. _Какое-то? Какого-то?_
Порой определения недостаточно, чтобы составить контракт. Необходимо уточнить определение класса типов.
Например, возьмем [полугруппу](https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D1%83%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0).

```dotty
trait Semigroup[A]:
  def combine(x: A, y: A): A
```

Полугруппа должна следовать следующим законам:

- _Замыкание_: для \\(\forall a, b \in S\\) выполняется \\(a + b \in S\\)
- _Ассоциативность_: для \\(\forall a, b, c \in S\\) выполняется \\((a + b) + c = a + (b + c)\\)

Первый закон можно гарантировать определением класса типов,
при условии, конечно же, использования при реализации только [чистых функций без побочных эффектов](https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D1%82%D0%BE%D1%82%D0%B0_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8).

Второй закон также можно гарантировать, определив соответствующий метод проверки:

```dotty
object Semigroup:
  def isSemigroup[A](x: A, y: A, z: A)(using sm: Semigroup[A]): Boolean =
    import sm.combine
    combine(x, combine(y, z)) == combine(combine(x, y), z)
```

Конечно, при условии, если бы мы могли запустить эту проверку на всех возможных элементах типа `A`
или хотя бы на достаточно большой выборке.
Потому что и для вычитания `isSemigroup(x, y, 0)` выдаст `true` для любых `x` и `y`, хотя вычитание не ассоциативно.

Например, целые числа с операцией умножения являются полугруппой и удовлетворяют законам полугруппы:

```dotty
given Semigroup[Int] = (x: Int, y: Int) => x * y
Semigroup[Int].combine(3, 5)
// val res0: Int = 15
```

> Тут надо быть осторожным из-за переполнения типа, которое может нарушить законы класса типов,
> но проигнорируем здесь этот момент.

Итак, класс типов может характеризоваться не только своим определением, но ещё и набором законов.

## Зачем нужны законы?

Поведение класса типов позволяет делать определенные выводы,
на которых, как на "кирпичиках", можно построить нечто большее чем исходное описание.

##### Замыкание

Например, какой вывод можно сделать из закона _"Замыкание"_?

Если мы можем "сложить" два элемента определенного типа и получить в результате элемент того же типа,
то это означает, что данную операцию можно проводить несколько раз над результатом предыдущего "сложения"!
Т.е. из "сложения" мы можем получить "умножение", из "умножения" - "возведение в степень" и т.д..

И у нас уже есть не только \\(3 * 5\\), но и \\(3^{5}\\):

```dotty
trait Semigroup[A]:
  def combine(x: A, y: A): A

  def combineN(x: A, n: Int :| Greater[0]): A =
    @tailrec def loop(b: A, k: Int, acc: A): A =
      if k == 1 then combine(b, acc)
      else
        val x = if (k & 1) == 1 then combine(b, acc) else acc
        loop(combine(b, b), k >>> 1, x)

    if n == 1 then x else loop(x, n - 1, x)
```

```dotty
Semigroup[Int].combineN(3, 5)
// val res1: Int = 243
```

> О том, что такое `Int :| Greater[0]` рассказывается в [статье об уточняющих типах](refined.md).

##### Ассоциативность

_"Ассоциативность"_ говорит о том, что мы можем складывать элементы в _любом_ порядке.
А значит, можем использовать этот факт там, где он полезен - при реализации класса типов!

Например, как свернуть коллекцию из миллиона элементов?
Разбить коллекцию пополам, параллельно свернуть каждую половину, а затем - "сложить" результаты?!
Для `Vector`-а - да, но будет ли это эффективно для связанного списка?!
Ответы на эти вопросы содержатся [во многих книгах](https://www.scalawithcats.com/dist/scala-with-cats.html#applications-of-monoids),
но здесь важно другое - что мы можем **выбирать**, как "складывать" элементы коллекции, если это "сложение" ассоциативно.

Т.о. законы классов типов помогают наиболее эффективно реализовать эти классы типов.

## Расширение подходящих типов

Поведение некоторых классов типов позволяет строить новые реализации на основе предыдущих.
Например,

```dotty
given nestedSemigroupInstance[A, B](using asm: Semigroup[A], bsm: Semigroup[B]): Semigroup[(A, B)] =
  (x: (A, B), y: (A, B)) => (asm.combine(x._1, y._1), bsm.combine(x._2, y._2))
```

Мы получили новую реализацию на основе существующих!
Конечно, это возможно не всегда и зависит от класса типов, но все же...

## Выводы

- Классы типов задают определенное поведение.
- Это поведение может задаваться как явно в коде, так и с помощью "соглашений",
  указанных в тестах, в документации или соблюдаемых "устно".
- Поведение позволяет "строить выводы", расширяющие класс типов как в сторону получения новой функциональности,
  так и в сторону увеличения множества подходящих типов.

Итак, вернёмся к началу: является ли классом типов следующее определение?

```dotty
trait Something[A, B]:
  def doSomething(x: A): B
```
